package org.lyc.dp;

/**
 * https://leetcode.cn/problems/get-maximum-in-generated-array/description/
 * 获取生成数组中的最大值
 * 给定一个整数n,按下列规则生成一个长度为n+1的整数, 0 <= n <= 100.
 * nums[0] = 0
 * nums[1] = 1
 * 当 2<=2*i<=n 时, n[2*i] = nums[i]
 * 当 2<=2*i+1<=n 时, n[2*i+1] = nums[i] + nums[i+1]
 * 例如:
 * 输入：n = 7
 * 输出：3
 * 解释：根据规则：
 * nums[0] = 0
 * nums[1] = 1
 * nums[(1 * 2) = 2] = nums[1] = 1
 * nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
 * nums[(2 * 2) = 4] = nums[2] = 1
 * nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
 * nums[(3 * 2) = 6] = nums[3] = 2
 * nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
 * 因此，nums = [0,1,1,2,1,3,2,3]，最大值 3
 * <p>
 * 输入：n = 2
 * 输出：1
 * 解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1
 * <p>
 * 输入：n = 3
 * 输出：2
 * 解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2
 * <p>
 * 此题目乍一看好像不是动态规划, 但是这一题只将状态转移方程写出来了而已. 状态转移方程完美诠释了状态机中状态跳转的概念.
 * 动态规划的本质是一个状态机, 从初始状态开始进行有向无环的跳转, 最后求得最终解.
 * @author Liu Yicong
 * @date 2024/2/2
 */
public class GGetMaximumGenerated {
	public static void main(String[] args) {
		System.out.println(getMaximumGenerated(0));
	}

	public static int getMaximumGenerated(int n) {
		if (n == 0) {
			return 0;
		}
		int[] nums = new int[n + 1];
		nums[0] = 0;
		nums[1] = 1;
		int i = 1;
		int max = 1;
		while (2 * i + 1 <= n) {
			nums[2 * i] = nums[i];
			nums[2 * i + 1] = nums[i] + nums[i + 1];
			if (nums[2 * i + 1] > max) {
				max = nums[2 * i + 1];
			}
			i++;
		}

		return max;
	}
}
